package leetcode;

import java.util.Arrays;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0279.java
 * @Author : WangRuoyu
 * @Date 2023/11/25 22:21
 */

public class Q0279 {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= i / k; k++) {
                f[i] = Math.min(f[i], f[i - k * k] + 1);
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
        Q0279 sl = new Q0279();
    }
}